import os

Tabuleiro = [[], [], [], [], [], [], [], []] # bidimensional 8x8
linha = [2, 1, -1, -2, -2, -1, 1, 2]
coluna = [1, 2, 2, 1, -1, -2, -2, -1]

os.system('clear' if os.name == 'posix' else 'cls')
tabuleiroSize = int (input('Informe o tamanho do tabuleiro (e.g. 8 para 8x8): '))
col = int(input('Informe a coluna de partida do cavalo: '))
lin = int(input('Informe a linha de partida do cavalo: '))
for lin in range(tabuleiroSize):
    for col in range(tabuleiroSize):
        Tabuleiro[lin].append(0)
limite = tabuleiroSize * tabuleiroSize


def init(l, c): # c de coluna; l de linha;
    Tabuleiro[l][c] = 1
    resultado = exerceMovimentos(2, l, c) # 2 = id de movimento
    if(resultado):
        imprimeFinal()
    else:
        print("Nao existe passeio possivel")

def exerceMovimentos(id, l, c): # função resposável por percorrer todas as possições e preenchelas
    resultado = id > limite # vai ser true ou false
    k = 0 # responsável por correr todos os possiveis movimentos
    while (not resultado and k < 8):
        x = l + linha[k]
        y = c + coluna[k] # x e y recebem o possível próximo movimento

        if(verificaMov(x, y)):
            Tabuleiro[x][y] = id
            resultado = exerceMovimentos(id + 1, x, y) # recursividade
            if(not resultado):
                Tabuleiro[x][y] = 0  # Descarta o movimento anterior em caso de falha.
        k += 1 # tenta próxima coordenada
    return resultado          


def verificaMov(x, y):
    return((y >= 0 and y < tabuleiroSize) and (x >= 0 and x < tabuleiroSize) and (Tabuleiro[x][y] == 0))

def imprimeFinal():
    os.system('clear' if os.name == 'posix' else 'cls')
    print('Caminho:')
    for i in range(tabuleiroSize):
        print(Tabuleiro[i])

init(lin, col)